{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Longest Nice Subarray"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: longestNiceSubarray"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最长优雅子数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个由 <strong>正</strong> 整数组成的数组 <code>nums</code> 。</p>\n",
    "\n",
    "<p>如果&nbsp;<code>nums</code> 的子数组中位于 <strong>不同</strong> 位置的每对元素按位 <strong>与（AND）</strong>运算的结果等于 <code>0</code> ，则称该子数组为 <strong>优雅</strong> 子数组。</p>\n",
    "\n",
    "<p>返回 <strong>最长</strong> 的优雅子数组的长度。</p>\n",
    "\n",
    "<p><strong>子数组</strong> 是数组中的一个 <strong>连续</strong> 部分。</p>\n",
    "\n",
    "<p><strong>注意：</strong>长度为 <code>1</code> 的子数组始终视作优雅子数组。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [1,3,8,48,10]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>最长的优雅子数组是 [3,8,48] 。子数组满足题目条件：\n",
    "- 3 AND 8 = 0\n",
    "- 3 AND 48 = 0\n",
    "- 8 AND 48 = 0\n",
    "可以证明不存在更长的优雅子数组，所以返回 3 。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [3,1,5,11,13]\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>最长的优雅子数组长度为 1 ，任何长度为 1 的子数组都满足题目条件。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [longest-nice-subarray](https://leetcode.cn/problems/longest-nice-subarray/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [longest-nice-subarray](https://leetcode.cn/problems/longest-nice-subarray/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,3,8,48,10]', '[3,1,5,11,13]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubarray(self, nums: List[int]) -> int:\n",
    "        sz = len(nums)\n",
    "        result = 0\n",
    "        for i in range(sz):\n",
    "            mask = 0\n",
    "            cnt = 0\n",
    "            for j in range(i, sz):\n",
    "                val = nums[j]\n",
    "                if mask & val == 0:\n",
    "                    mask |= val\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    break\n",
    "            result = max(result, cnt)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubarray(self, nums: List[int]) -> int:\n",
    "        ans, l = 1, 0\n",
    "        for r, num in enumerate(nums):\n",
    "            cur = l\n",
    "            for i in range(l, r):\n",
    "                if nums[i]&num != 0:\n",
    "                    cur = i + 1\n",
    "            l = cur\n",
    "            ans = max(ans, r - l + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubarray(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for i, or_ in enumerate(nums):  # 枚举子数组右端点 i\n",
    "            j = i - 1\n",
    "            while j >= 0 and (or_ & nums[j]) == 0:  # nums[j] 与子数组中的任意元素 AND 均为 0\n",
    "                or_ |= nums[j]  # 加到子数组中\n",
    "                j -= 1  # 向左扩展\n",
    "            ans = max(ans, i - j)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubarray(self, nums: List[int]) -> int:\n",
    "        l = mask = 0\n",
    "        res = 1\n",
    "        for r, x in enumerate(nums):\n",
    "            while mask & x != 0:\n",
    "                mask ^= nums[l]\n",
    "                l += 1\n",
    "            mask |= x\n",
    "            res = max(res, r - l + 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubarray(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for i, or_ in enumerate(nums):  # 枚举子数组右端点 i\n",
    "            j = i - 1\n",
    "            while j >= 0 and (or_ & nums[j]) == 0:  # nums[j] 与子数组中的任意元素 AND 均为 0\n",
    "                or_ |= nums[j]  # 加到子数组中\n",
    "                j -= 1  # 向左扩展\n",
    "            ans = max(ans, i - j)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubarray(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        left = 0\n",
    "        flag = 0\n",
    "\n",
    "        for right, x in enumerate(nums):\n",
    "            while flag & x:\n",
    "                flag ^= nums[left]\n",
    "                left += 1\n",
    "\n",
    "            flag |= x\n",
    "            res = max(res, right - left + 1)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubarray(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        result = 1\n",
    "        for i in range(n):\n",
    "            tmp = nums[i]\n",
    "            for j in range(i-1,-1,-1):\n",
    "                if(tmp & nums[j] > 0):\n",
    "                    break\n",
    "                tmp = tmp | nums[j]\n",
    "                result = max(result, i-j+1)\n",
    "        return result\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def longestNiceSubarray(self, nums: List[int]) -> int:\r\n",
    "        n = len(nums)\r\n",
    "        lf = 0\r\n",
    "        or_ = 0\r\n",
    "        ans = 0\r\n",
    "        for rt,n in enumerate(nums):\r\n",
    "            while or_ & n:\r\n",
    "                or_ ^= nums[lf]\r\n",
    "                lf += 1\r\n",
    "            or_ |= n\r\n",
    "            ans = max(ans, rt - lf + 1)\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubarray(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        l = r = s = ans = 0\n",
    "        while r < n:\n",
    "            while nums[r] & s:\n",
    "                s -= nums[l]\n",
    "                l += 1\n",
    "            s |= nums[r]\n",
    "            ans = max(ans, r - l + 1)\n",
    "            r += 1\n",
    "        return ans\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubarray(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for i,or_ in enumerate(nums):\n",
    "            j = i-1\n",
    "            while j >= 0 and (or_ & nums[j])==0:\n",
    "                or_ |= nums[j]\n",
    "                j -= 1\n",
    "            ans = max(ans,i-j)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubarray(self, nums: List[int]) -> int:\n",
    "        result, j, cur = 1, 0, 0\n",
    "        for i, x in enumerate(nums):\n",
    "            while x & cur:\n",
    "                cur ^= nums[j]\n",
    "                j += 1\n",
    "            result = max(result, i - j + 1)\n",
    "            cur ^= x\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubarray(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        l, r, s = 0, 0, 0\n",
    "        n = len(nums)\n",
    "        while r < n:\n",
    "            while s | nums[r] != s + nums[r]:\n",
    "                s -= nums[l]\n",
    "                l += 1\n",
    "            s += nums[r]\n",
    "            ans = max(ans, r - l + 1)\n",
    "            r += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubarray(self, nums: List[int]) -> int:\n",
    "        ret = 1\n",
    "        n = len(nums)\n",
    "        q = deque()\n",
    "        cnt = [0] * 30\n",
    "        for i in range(n):\n",
    "            x = nums[i]\n",
    "            for j in range(30):\n",
    "                cnt[j] += x >> j & 1\n",
    "            q.append(x)\n",
    "            while True:\n",
    "                for j in range(30):\n",
    "                    if cnt[j] > 1:\n",
    "                        y = q.popleft()\n",
    "                        for j in range(30):\n",
    "                            cnt[j] -= y >> j & 1\n",
    "                        break\n",
    "                else:\n",
    "                    break\n",
    "            ret = max(ret, len(q))\n",
    "        return ret\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubarray(self, nums: List[int]) -> int:\n",
    "        ans = left = or_ = 0\n",
    "        for right,x in enumerate(nums):\n",
    "            while or_ & x:\n",
    "                or_ ^= nums[left]\n",
    "                left += 1\n",
    "            or_ |= x\n",
    "            ans = max(ans,right-left+1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubarray(self, nums: List[int]) -> int:\n",
    "        lastLen, lastMask, res = 0, 0, 0\n",
    "        for i, n in enumerate(nums):\n",
    "            if lastMask & n == 0:\n",
    "                lastLen += 1\n",
    "                lastMask = lastMask | n\n",
    "                res = max(res, lastLen)\n",
    "                continue\n",
    "            for l in range(i - lastLen, i):\n",
    "                lastMask ^= nums[l]\n",
    "                if lastMask & n == 0:\n",
    "                    lastMask |= n\n",
    "                    lastLen = i - l\n",
    "                    break\n",
    "            else:\n",
    "                lastLen, lastMask = 1, n\n",
    "        return res\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubarray(self, nums: List[int]) -> int:\n",
    "        ans=1\n",
    "        dig=0\n",
    "        #result of or\n",
    "        i=j=0\n",
    "        n=len(nums)\n",
    "        while j<n:\n",
    "            while dig & nums[j]!=0:\n",
    "                dig^=nums[i]\n",
    "                i+=1\n",
    "            dig|=nums[j]\n",
    "            j+=1\n",
    "            ans=max(ans,j-i)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubarray(self, nums: List[int]) -> int:\n",
    "        #滑动窗口与 &运算符\n",
    "        ans=0\n",
    "        mask=0\n",
    "        left=0\n",
    "        for right,num in enumerate(nums):\n",
    "            while mask & num >0:\n",
    "                mask^=nums[left]#在python中^符号代表按位翻转\n",
    "                left+=1\n",
    "            mask^=num\n",
    "            ans=max(ans, right-left+1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubarray(self, nums: List[int]) -> int:\n",
    "        ans = left = or_ = 0\n",
    "        for right, x in enumerate(nums):\n",
    "            while or_ & x:  # 有交集\n",
    "                or_ ^= nums[left]  # 从 or_ 中去掉集合 nums[left]\n",
    "                left += 1\n",
    "            or_ |= x  # 把集合 x 并入 or_ 中\n",
    "            ans = max(ans, right - left + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubarray(self, nums: List[int]) -> int:\n",
    "        #滑动窗口\n",
    "        n=len(nums)\n",
    "        l,pre=0,nums[0]\n",
    "        ans=1\n",
    "        for r in range(1,n):\n",
    "            while nums[r]&pre and l<r:\n",
    "                pre^=nums[l]\n",
    "                l+=1\n",
    "            pre|=nums[r]\n",
    "            ans=max(ans,r-l+1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubarray(self, nums: List[int]) -> int:\n",
    "        '''\n",
    "        n = len(nums)\n",
    "        result = 1\n",
    "        for i in range(n):\n",
    "            tmp = nums[i]\n",
    "            for j in range(i-1,-1,-1):\n",
    "                if(tmp & nums[j] > 0):\n",
    "                    break\n",
    "                tmp = tmp | nums[j]\n",
    "                result = max(result, i-j+1)\n",
    "        return result\n",
    "        '''\n",
    "        n = len(nums)\n",
    "        result = 1\n",
    "        tmp = 0\n",
    "        left, right = 0, 0\n",
    "        while(right < n):\n",
    "            while(left <= right and tmp & nums[right]  > 0):\n",
    "                tmp = tmp & (~nums[left])\n",
    "                left += 1\n",
    "            tmp = tmp | nums[right]\n",
    "            result = max(result, right-left+1)\n",
    "            right += 1\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubarray(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for i,or_ in enumerate(nums):\n",
    "            j = i - 1\n",
    "            while j >= 0 and or_ & nums[j] == 0:\n",
    "                or_ |= nums[j]\n",
    "                j -= 1\n",
    "            ans = max(ans,i - j)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubarray(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        \n",
    "        dicc=defaultdict(int)\n",
    "        \n",
    "        \n",
    "        left=0\n",
    "        ans=1\n",
    "        \n",
    "        for i in range(n):\n",
    "            s=bin(nums[i])[2:][::-1]\n",
    "            for j in range(len(s)):\n",
    "                dicc[j]+=1 if s[j]=='1' else 0\n",
    "                \n",
    "            while max(dicc.values())>1:\n",
    "                s=bin(nums[left])[2:][::-1]\n",
    "                for j in range(len(s)):\n",
    "                    dicc[j]-=1 if s[j]=='1' else 0\n",
    "                left+=1\n",
    "            ans=max(ans,i-left+1)\n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        return ans\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubarray(self, nums: List[int]) -> int:\n",
    "        res = l = 0\n",
    "        ors = 0\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            while ors & nums[i] != 0:\n",
    "                ors ^= nums[l]\n",
    "                l += 1\n",
    "            ors |= nums[i]\n",
    "            res = max(res, i - l + 1)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubarray(self, nums: List[int]) -> int:\n",
    "        ans = 1\n",
    "        l, r, n = 0, 1, len(nums)\n",
    "        \n",
    "        while r < n:\n",
    "            for i in range(l, r):\n",
    "                if nums[i] & nums[r]:\n",
    "                    l = i + 1\n",
    "            ans = max(ans, r - l + 1)\n",
    "            r += 1\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubarray(self, nums: List[int]) -> int:\n",
    "        l = 0\n",
    "        r = 0\n",
    "        ans = 1\n",
    "        while r < len(nums):\n",
    "            tmp = l\n",
    "            while tmp < r:\n",
    "                if nums[tmp] & nums[r]:\n",
    "                    l = tmp + 1\n",
    "                tmp += 1\n",
    "            if r - l + 1 > ans:\n",
    "                ans = r -l + 1\n",
    "            r += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubarray(self, nums: List[int]) -> int:\n",
    "        ans = left = or_ = 0\n",
    "        for right,x in enumerate(nums):\n",
    "            while or_ & x:\n",
    "                or_ ^= nums[left]\n",
    "                left += 1\n",
    "            or_ |= x\n",
    "            ans = max(ans,right - left + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubarray(self, nums: List[int]) -> int:\n",
    "        # 判断新加的数字能否和之前的数组构成优雅子数组\n",
    "        def andlist(nums,new):\n",
    "            # 由于已经加入了新数字，需要特殊处理\n",
    "            if nums.count(new) != 1:\n",
    "                return 0\n",
    "            res = 1\n",
    "            for i in range(len(nums)):\n",
    "                if nums[i] != new and nums[i] & new !=0:\n",
    "                    res = 0\n",
    "                    break\n",
    "            return res   \n",
    "        n = len(nums)\n",
    "        left,right = 0, 0\n",
    "        res = 0\n",
    "        window = []\n",
    "        while right < n:\n",
    "            window.append(nums[right])\n",
    "            while window and not andlist(window,nums[right]):\n",
    "                window.pop(0)\n",
    "                left += 1\n",
    "            right += 1\n",
    "            res = max(res,right - left)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubarray(self, nums: List[int]) -> int:\n",
    "        \n",
    "        ans = 0\n",
    "        mask = 0\n",
    "        left = 0\n",
    "        for right, num in enumerate(nums):\n",
    "            \n",
    "            while mask & num > 0:       # 窗口左端元素滑出\n",
    "                mask ^= nums[left]      # 去除左端元素nums[left]\n",
    "                left += 1               # 左端口右移\n",
    "            \n",
    "            mask |= num                 # 当前元素加入mask\n",
    "            ans = max(ans, right-left+1)\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubarray(self, nums: List[int]) -> int:\n",
    "        ret = 1\n",
    "        for i in range(len(nums)):\n",
    "            count = 1\n",
    "            temp = nums[i]\n",
    "            for j in range(i+1, len(nums)):\n",
    "                if temp & nums[j] == 0:\n",
    "                    count += 1\n",
    "                    temp = temp | nums[j]\n",
    "                else:\n",
    "                    break\n",
    "            ret = max(ret, count)\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubarray(self, nums: List[int]) -> int:\n",
    "        mask=0\n",
    "        ans=0\n",
    "        l=0\n",
    "        n=len(nums)\n",
    "        for r in range(n):\n",
    "            while mask & nums[r]:\n",
    "                mask^=nums[l]\n",
    "                l+=1\n",
    "            mask|=nums[r]\n",
    "            ans=max(ans,r-l+1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubarray(self, nums: List[int]) -> int:\n",
    "        ans = left = or_ = 0\n",
    "        for right, x in enumerate(nums):\n",
    "            while or_ & x:  # 有交集\n",
    "                or_ ^= nums[left]  # 从 or_ 中去掉集合 nums[left]\n",
    "                left += 1\n",
    "            or_ |= x  # 把集合 x 并入 or_ 中\n",
    "            ans = max(ans, right - left + 1)\n",
    "        return ans\n",
    "\n",
    "nums=[3,1,5,11,13]\n",
    "\n",
    "solution = Solution()\n",
    "result = solution.longestNiceSubarray(nums)\n",
    "print(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubarray(self, nums: List[int]) -> int:\n",
    "        #滑动窗口+位运算\n",
    "        n=len(nums)\n",
    "        l,pre=0,nums[0]\n",
    "        ans=1\n",
    "        for r in range(1,n):\n",
    "            while nums[r]&pre and l<r:\n",
    "                pre^=nums[l]\n",
    "                l+=1\n",
    "            pre|=nums[r]\n",
    "            ans=max(ans,r-l+1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubarray(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        l = 0\n",
    "        mask = 0\n",
    "        res = 0\n",
    "        for r in range(n):\n",
    "            while l <= r and mask & nums[r]:\n",
    "                mask ^= nums[l]\n",
    "                l += 1 \n",
    "            res = max(res, r - l + 1)\n",
    "            mask |= nums[r]\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubarray(self, nums: List[int]) -> int:\n",
    "        ans=1\n",
    "        dig=0\n",
    "        #result of or\n",
    "        i=j=0\n",
    "        n=len(nums)\n",
    "        while i<n:\n",
    "            while j<n and (dig & nums[j]==0):\n",
    "                #没有重复的1\n",
    "                dig|=nums[j]\n",
    "                j+=1\n",
    "            ans=max(ans,j-i)\n",
    "            if j==n:\n",
    "                break\n",
    "            #子数组中断\n",
    "            while i<j and(dig & nums[j]!=0):\n",
    "                dig^=nums[i]\n",
    "                i+=1\n",
    "                #remove\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubarray(self, nums: List[int]) -> int:\n",
    "        l = 0\n",
    "        r = 0\n",
    "        res = 0\n",
    "        while r < len(nums):\n",
    "            tmp = nums[r]\n",
    "            for i in range(r - 1, l - 1, -1):\n",
    "                if nums[i] & tmp != 0:\n",
    "                    l = i+1\n",
    "                    break\n",
    "                      # 更新 l 的值\n",
    "            res = max(res, r - l + 1)\n",
    "            r += 1\n",
    "        return res\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubarray(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        i, j = 0, 0\n",
    "        r = 0\n",
    "        ans = 1\n",
    "        while i < n and j < n:\n",
    "            while j < n and nums[j] & r == 0:\n",
    "                r |= nums[j]\n",
    "                j += 1\n",
    "            ans = max(ans, j-i)\n",
    "            if j >= n:\n",
    "                break\n",
    "            while i < j and nums[j] & r != 0:\n",
    "                r ^= nums[i]\n",
    "                i += 1\n",
    "            r |= nums[j]\n",
    "            j += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubarray(self, nums: List[int]) -> int:\n",
    "        mask=0\n",
    "        ans=0\n",
    "        l=0\n",
    "        n=len(nums)\n",
    "        for r in range(n):\n",
    "            \n",
    "            while mask & nums[r]:\n",
    "                mask^=nums[l]\n",
    "                l+=1\n",
    "            mask|=nums[r]\n",
    "            ans=max(ans,r-l+1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubarray(self, nums: List[int]) -> int:\n",
    "        l = 0\n",
    "        r = 0\n",
    "        res = 0\n",
    "        while r < len(nums):\n",
    "            for i in range(r - 1, l - 1, -1):\n",
    "                if nums[i] & nums[r] != 0:\n",
    "                    l = i+1 # 更新 l 的值\n",
    "                    break\n",
    "            res = max(res, r - l + 1)\n",
    "            r += 1\n",
    "        return res\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubarray(self, nums: List[int]) -> int:\n",
    "        ans = j = mask = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            while mask & x:             # 有交集\n",
    "                mask ^= nums[j]         # 将nums[j]从mask中移除\n",
    "                j += 1\n",
    "            mask |= x                   # 将x并上mask\n",
    "            ans = max(ans, i - j + 1)   # 更新最长的ans\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubarray(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        left = 0 \n",
    "        or_ = 0\n",
    "        for right, num in enumerate(nums):\n",
    "            while or_ & num:\n",
    "                or_ ^= nums[left]\n",
    "                left += 1\n",
    "            or_ |= num\n",
    "            ans = max(ans, right - left + 1)\n",
    "        return ans\n",
    "\n",
    "\n",
    "        # ans = 0\n",
    "        # for i, or_ in enumerate(nums):\n",
    "        #     j = i - 1\n",
    "        #     while j >= 0 and or_ & nums[j] == 0:\n",
    "        #         or_ |= nums[j]\n",
    "        #         j -= 1\n",
    "        #     ans = max(ans, i - j)\n",
    "        # return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "元素集合对应的交集为空\n",
    "不断添加right，判断是否需要移动left，每次的答案均为right-left+1\n",
    "位运算的巧妙融合\n",
    "'''\n",
    "class Solution:\n",
    "    def longestNiceSubarray(self, nums: List[int]) -> int:\n",
    "        #相向双指针怎么写来着？\n",
    "        #判断当前元素与之前元素的or_值相与是否为0,为0则可以加入\n",
    "        or_=nums[0]\n",
    "        l=0\n",
    "        r=0\n",
    "        ans=1\n",
    "        for r in range(1,len(nums)):\n",
    "            while or_&nums[r]:\n",
    "                or_^=nums[l]\n",
    "                l+=1\n",
    "            or_|=nums[r]\n",
    "            ans = max(ans, r-l+ 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubarray(self, nums: List[int]) -> int:\n",
    "        # 按照按位与和集合的特性做\n",
    "        # 如果没用交集才能为0\n",
    "        i, ans, _or = 0, 0, 0\n",
    "        for j, x in enumerate(nums):\n",
    "            while _or & x != 0:\n",
    "                # 删除集合中的子集 nums[i]\n",
    "                _or ^= nums[i]\n",
    "                i += 1\n",
    "            # 加入集合\n",
    "            _or |= x\n",
    "            ans = max(ans, j - i + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubarray(self, nums: List[int]) -> int:\n",
    "        cnt = [-1] * 32\n",
    "        dp = [-1] * len(nums)\n",
    "        ans = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            for j in range(32):\n",
    "                if (x >> j) & 1:\n",
    "                    dp[i] = max(dp[i], cnt[j])\n",
    "                    cnt[j] = i\n",
    "            if i != 0:\n",
    "                dp[i] = max(dp[i], dp[i - 1])\n",
    "            ans = max(ans, i - dp[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubarray(self, nums: List[int]) -> int:\n",
    "        res = 1\n",
    "        count = 1\n",
    "\n",
    "        i = 0\n",
    "        j = 1\n",
    "\n",
    "        temp = nums[i]\n",
    "\n",
    "        while i < j and j < len(nums):\n",
    "            slow = nums[i]\n",
    "            fast = nums[j]\n",
    "\n",
    "            if temp & fast == 0:\n",
    "                temp |= fast\n",
    "                count += 1\n",
    "                j += 1\n",
    "            else:\n",
    "                if j - i == 1:\n",
    "                    i += 1\n",
    "                    j += 1\n",
    "                    temp = nums[i]\n",
    "                    count = 1\n",
    "                else:\n",
    "                    temp ^= slow\n",
    "                    i += 1\n",
    "                    count -= 1\n",
    "\n",
    "            if count > res:\n",
    "                res = count\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubarray(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        left = 0\n",
    "        s = 0\n",
    "        ans = 1\n",
    "        for right, num in enumerate(nums):\n",
    "            while s and num & s:\n",
    "                s ^= nums[left]\n",
    "                left += 1\n",
    "            s |= num\n",
    "            ans = max(ans, right - left + 1)\n",
    "        return ans\n",
    "            \n",
    "            \n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubarray(self, nums: List[int]) -> int:\n",
    "        ans = 1\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            mask = 0xffffffff\n",
    "            for j in range(i, n):\n",
    "                if nums[j] & mask != nums[j]:\n",
    "                    break\n",
    "                mask &= ~nums[j]\n",
    "                ans = max(ans, j - i + 1)\n",
    "            if n - i <= ans:\n",
    "                break\n",
    "            \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubarray(self, nums: List[int]) -> int:\n",
    "        ans=1\n",
    "        l=0\n",
    "        or_=0\n",
    "        for r,x in enumerate(nums):\n",
    "            while or_&x:\n",
    "                or_^=nums[l]\n",
    "                l+=1\n",
    "            or_|=x\n",
    "            ans=max(ans,r-l+1)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubarray(self, nums: List[int]) -> int:\n",
    "        '''\n",
    "        n = len(nums)\n",
    "        result = 1\n",
    "        for i in range(n):\n",
    "            tmp = nums[i]\n",
    "            for j in range(i-1,-1,-1):\n",
    "                if(tmp & nums[j] > 0):\n",
    "                    break\n",
    "                tmp = tmp | nums[j]\n",
    "                result = max(result, i-j+1)\n",
    "        return result\n",
    "        '''\n",
    "        n = len(nums)\n",
    "        result = 1\n",
    "        tmp = 0\n",
    "        left, right = 0, 0\n",
    "        while(right < n):\n",
    "            while(left <= right and tmp & nums[right]  > 0):\n",
    "                tmp = tmp & (~nums[left])\n",
    "                left += 1\n",
    "            tmp = tmp | nums[right]\n",
    "            result = max(result, right-left+1)\n",
    "            right += 1\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubarray(self, nums: List[int]) -> int:\n",
    "        ans = left = or_ = 0\n",
    "        for right, x in enumerate(nums):\n",
    "            while or_ & x:  # 有交集\n",
    "                or_ ^= nums[left]  # 从 or_ 中去掉集合 nums[left]\n",
    "                left += 1\n",
    "            or_ |= x  # 把集合 x 并入 or_ 中\n",
    "            ans = max(ans, right - left + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubarray(self, nums: List[int]) -> int:\n",
    "        ans = left = s = 0\n",
    "        for r, x in enumerate(nums):\n",
    "            while s & x:\n",
    "                s ^= nums[left]\n",
    "                left += 1\n",
    "            s ^= x\n",
    "            ans = max(ans, r - left + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubarray(self, nums: List[int]) -> int:\n",
    "        # nums = [3,8,48]\n",
    "        pre_or = 0\n",
    "        ans = 0\n",
    "        left = 0\n",
    "        for j,v in enumerate(nums):  \n",
    "            while v & pre_or:\n",
    "                pre_or ^= nums[left]\n",
    "                left += 1\n",
    "            pre_or |= v\n",
    "            ans = max(ans, j - left + 1)\n",
    "        print(ans)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubarray(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        left = 0\n",
    "        s = 0\n",
    "        ans = 1\n",
    "        for right, num in enumerate(nums):\n",
    "            while s and num & s != 0:\n",
    "                s ^= nums[left]\n",
    "                left += 1\n",
    "            s |= num\n",
    "            ans = max(ans, right - left + 1)\n",
    "        return ans\n",
    "            \n",
    "            \n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubarray(self, nums: List[int]) -> int:\n",
    "        ans = left = or_ = 0\n",
    "        for right, x in enumerate(nums):\n",
    "            while or_ & x:  # 有交集\n",
    "                or_ ^= nums[left]  # 从 or_ 中去掉集合 nums[left]\n",
    "                left += 1\n",
    "            or_ |= x  # 把集合 x 并入 or_ 中\n",
    "            ans = max(ans, right - left + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubarray(self, nums: List[int]) -> int:\n",
    "        ans = left = or_ = 0\n",
    "        for right, x in enumerate(nums):\n",
    "            while or_ & x:\n",
    "                or_ ^= nums[left]\n",
    "                left += 1\n",
    "            or_ |= x\n",
    "            ans = max(ans, right - left + 1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubarray(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        # 枚举窗口右指针j\n",
    "        for j in range(len(nums)):\n",
    "            i = j - 1 # 枚举窗口左指针i\n",
    "            while i >= 0: # 检查nums[i]能否加入窗口\n",
    "                flag = False\n",
    "                for k in range(i + 1, j + 1): # 枚举窗口内已有元素nums[k]\n",
    "                    if (nums[i] & nums[k]) != 0:\n",
    "                        flag = True # 与窗口内已有元素AND运算后不为0\n",
    "                        break\n",
    "                if flag: # 不能加入窗口\n",
    "                    break\n",
    "                i -= 1\n",
    "            res = max(res, j - i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubarray(self, nums: List[int]) -> int:\n",
    "        left = 0\n",
    "        right = 0\n",
    "        cnt = [0] * 30\n",
    "        def check():\n",
    "            for c in cnt:\n",
    "                if c > 1:\n",
    "                    return False\n",
    "            return True\n",
    "        ans = 0\n",
    "        N = len(nums)\n",
    "        while(right < N):\n",
    "            num = nums[right]\n",
    "            idx = 0\n",
    "            while(num!=0):\n",
    "                cnt[-(idx+1)]+=(num&1)\n",
    "                idx+=1\n",
    "                num >>=1\n",
    "            while(not check()):\n",
    "                l_num = nums[left]\n",
    "                idx = 0\n",
    "                while(l_num!=0):\n",
    "                    cnt[-(idx+1)]-=(l_num&1)\n",
    "                    idx+=1\n",
    "                    l_num >>=1\n",
    "                left+=1\n",
    "            ans = max(ans, right-left+1)\n",
    "            right+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubarray(self, nums: List[int]) -> int:\n",
    "        l = 0\n",
    "        r = 0\n",
    "        res = 0\n",
    "        while r < len(nums):\n",
    "            for i in range(r - 1, l - 1, -1):\n",
    "                print(r)\n",
    "                print(l)\n",
    "                if nums[i] & nums[r] != 0:\n",
    "                    l = i+1 # 更新 l 的值\n",
    "                    break\n",
    "            res = max(res, r - l + 1)\n",
    "            r += 1\n",
    "        return res\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubarray(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        xor, i, ans = 0, 0, 0\n",
    "\n",
    "        for j in range(n):\n",
    "            x = nums[j]\n",
    "            while xor & x != 0:\n",
    "                xor ^= nums[i]\n",
    "                i += 1\n",
    "            xor |= x\n",
    "\n",
    "            ans = max(ans, j - i + 1)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubarray(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        left=temp=0\n",
    "        res=0\n",
    "        for right in range(n):\n",
    "            \n",
    "            while temp&nums[right]:\n",
    "                temp^=nums[left]\n",
    "                left+=1 \n",
    "            temp|=nums[right] \n",
    "            res=max(res,right-left+1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubarray(self, nums: List[int]) -> int:\n",
    "        res = 1\n",
    "        l, r = 0, 0\n",
    "        c = 0\n",
    "        while l < len(nums):\n",
    "            while r < len(nums) and nums[r] & c == 0:\n",
    "                c |= nums[r]\n",
    "                r += 1\n",
    "                res = max(res, r - l)\n",
    "            c ^= nums[l]\n",
    "            l += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubarray(self, nums: List[int]) -> int:\n",
    "        ans = l = r = or_ = 0\n",
    "        for r, x in enumerate(nums):\n",
    "            while or_ & nums[r]:\n",
    "                or_ ^= nums[l]\n",
    "                l += 1\n",
    "            or_ |= nums[r]\n",
    "            r += 1\n",
    "            ans = max(ans, r - l)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubarray(self, nums: List[int]) -> int:\n",
    "        # dp[i] 以i结尾的最长优雅子数组,想要和前面所有数字都and0，那么要与前面的异或为0\n",
    "        left = 0\n",
    "        yihuo = 0\n",
    "        res = -inf \n",
    "        for right in range(len(nums)):\n",
    "            vaild = yihuo&nums[right]\n",
    "            while vaild != 0:\n",
    "                yihuo = yihuo ^ nums[left]\n",
    "                vaild = yihuo & nums[right]\n",
    "                left += 1\n",
    "            yihuo = yihuo ^ nums[right]\n",
    "            res = max(res,right-left+1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubarray(self, nums: List[int]) -> int:\n",
    "\n",
    "\n",
    "\n",
    "        \"\"\"\n",
    "            1 0 0\n",
    "            * _ _\n",
    "            0 1 1\n",
    "        \n",
    "        一旦一个bit为1 后续这里都不能再有人，可以滑动窗口？\n",
    "        \"\"\"\n",
    "\n",
    "        mask = 0\n",
    "        l = 0\n",
    "        n = len(nums)\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            # []\n",
    "            while mask & nums[i]:\n",
    "                # 一直收缩左边界\n",
    "                mask ^= nums[l]\n",
    "                l += 1\n",
    "            \n",
    "            mask ^= nums[i]\n",
    "            res = max(res, i-l+1)\n",
    "        return res\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubarray(self, nums: List[int]) -> int:\n",
    "        count = [0] * 32\n",
    "        l, res = 0, 0\n",
    "        for r, n in enumerate(nums):\n",
    "            for i in range(32):\n",
    "                if (n >> i) & 1:\n",
    "                    count[i] += 1\n",
    "            while any(x > 1 for x in count):\n",
    "                for i in range(32):\n",
    "                    if (nums[l] >> i) & 1:\n",
    "                        count[i] -= 1\n",
    "                l += 1\n",
    "            res = max(res, r - l + 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubarray(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        left = 0\n",
    "        right = 1\n",
    "        max_length = 1\n",
    "        while right < n:\n",
    "            if nums[left] & nums[right] == 0:\n",
    "                flag = True\n",
    "                for i in range(left+1,right):\n",
    "                    if nums[i] & nums[right] != 0:\n",
    "                        flag = False\n",
    "                if flag:\n",
    "                    max_length = max(max_length, right - left + 1)\n",
    "                    right += 1\n",
    "                else:\n",
    "                    left += 1\n",
    "            else:\n",
    "                if left< right:\n",
    "                    left += 1\n",
    "                else:\n",
    "                    right += 1\n",
    "        return max_length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubarray(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for i, or_ in enumerate(nums):  # 枚举子数组右端点 i\n",
    "            j = i - 1\n",
    "            while j >= 0 and (or_ & nums[j]) == 0:  # nums[j] 与子数组中的任意元素 AND 均为 0\n",
    "                or_ |= nums[j]  # 加到子数组中\n",
    "                j -= 1  # 向左扩展\n",
    "            ans = max(ans, i - j)\n",
    "        return ans\n",
    "                    \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubarray(self, nums: List[int]) -> int:\n",
    "        ans = 1\n",
    "        s = 0\n",
    "        l = 0\n",
    "        for r, num in enumerate(nums):\n",
    "            while l < r and num & s:\n",
    "                s ^= nums[l]\n",
    "                l += 1\n",
    "            s |= num\n",
    "            ans = max(ans, r - l + 1)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubarray(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for i, or_ in enumerate(nums):  # 枚举子数组右端点 i\n",
    "            j = i - 1\n",
    "            while j >= 0 and (or_ & nums[j]) == 0:  # nums[j] 与子数组中的任意元素 AND 均为 0\n",
    "                or_ |= nums[j]  # 加到子数组中\n",
    "                j -= 1  # 向左扩展\n",
    "            ans = max(ans, i - j)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubarray(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        mask = 0\n",
    "        left = 0\n",
    "        for right, num in enumerate(nums):\n",
    "            \n",
    "            while mask & num > 0:       # 窗口左端元素滑出\n",
    "                mask ^= nums[left]      # 去除左端元素nums[left]\n",
    "                left += 1               # 左端口右移\n",
    "            \n",
    "            mask ^= num                 # 当前元素加入mask\n",
    "            ans = max(ans, right-left+1)\n",
    "        \n",
    "        return ans\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
